#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while (ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while (x);
	while (__top) putchar(__stk[__top--] + '0');
}

const int mod = 998244353;

void Min(int &x, int y) { y < x and (x = y); }
void Max(int &x, int y) { y > x and (x = y); }

void inc(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = 1ll * x * y % mod; }

int q_pow(int x, int k) { int res = 1; for (; k; k >>= 1, mul(x, x)) if (k & 1) mul(res, x); return res; }

bool stmer;

const int N = 1e5 + 10;
const int inf = 1e9;

int n, q;
int f[N], g[N];

vector<int> op[N];

struct node {
    int l, r;
    int calc(int L, int R) {
        if (R <= l or L >= r) return 0;
        if (L >= l and R <= r) return 1;
        if (L <= l and R >= r) return R - r + l - L;
        return L < l ? min(R - l, l - L) : min(r - L, R - r);
    }
} a[N];

namespace SEG {
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define mid ((l + r) >> 1)
    
    struct node {
        int l, r, cnt;
        node operator + (const node &p) const { return { l + p.l, r + p.r, cnt + p.cnt }; }
        node operator - (const node &p) const { return { l - p.l, r - p.r, cnt - p.cnt }; }
        node operator += (const node &p) { return *this = *this + p; }
    };

    struct tree {
        int ls, rs;
        node p;
    } t[N * 20];

    int cnt;
    int rt[N];

    int New(int lr) { return t[++cnt] = t[lr], cnt; }

    void modify(int l, int r, int x, int y, int &lr) {
        lr = New(lr), t[lr].p += { x, y, 1 }; if (l == r) return;
        mid >= x ? modify(l, mid, x, y, ls(lr)) : modify(mid + 1, r, x, y, rs(lr));
    }

    node query(int l, int r, int L, int R, int x, int y) {
        if (l >= L and r <= R) return t[y].p - t[x].p;
        if (mid >= L and mid < R) return query(l, mid, L, R, ls(x), ls(y)) + query(mid + 1, r, L, R, rs(x), rs(y));
        return mid >= L ? query(l, mid, L, R, ls(x), ls(y)) : query(mid + 1, r, L, R, rs(x), rs(y));
    }

    node ask(int l, int r, int L, int R) {
        if (l > r or L > R) return { 0, 0 };
        return query(1, n, l, r, rt[L - 1], rt[R]); 
    }

    void init() {
        for (int i = 1; i <= n; i++) {
            rt[i] = rt[i - 1];
            for (int x : op[i]) modify(1, n, x, i, rt[i]);
        }
    }

    #undef mid
}

int calc(int L, int R) {
    int res = f[L], mid = (L + R) >> 1;
    res += SEG :: ask(1, L, R, n).cnt;
    SEG :: node tmp = SEG :: ask(L, R, L, R);
    res += tmp.cnt * (R - L) - tmp.r + tmp.l;
    tmp = SEG :: ask(L + 1, mid, R + 1, n), res += tmp.l - tmp.cnt * L;
    tmp = SEG :: ask(mid + 1, R, R + 1, n), res += tmp.cnt * R - tmp.l;
    tmp = SEG :: ask(1, L - 1, L, mid), res += tmp.r - tmp.cnt * L;
    tmp = SEG :: ask(1, L - 1, mid + 1, R - 1), res += tmp.cnt * R - tmp.r;
    return res;
}

bool edmer;
signed main() {
	freopen("block.in", "r", stdin);
	freopen("block.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
	
    n = read(), q = read();
    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        op[r].push_back(l);
    }

    SEG :: init();

    for (int i = 1; i <= n; i++) {
        int l = 0, r = i - 1, res = inf;
        while (l + 10 <= r) {
            int mid1 = (l + l + r) / 3, mid2 = (l + r + r) / 3;
            calc(mid1, i) <= calc(mid2, i) ? r = mid2 : l = mid1;
        }
        for (int j = l; j <= r; j++) {
            int val = calc(j, i);
            if (val <= res) res = val, g[i] = j;
        }
        l = max(1ll, g[i - 1] - 10), r = min(i - 1, g[i - 1] + 10);
        for (int j = l; j <= r; j++) {
            int val = calc(j, i);
            if (val <= res) res = val, g[i] = j;
        }
        f[i] = res;
    }

    write(f[n]);

    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds\n";
	return 0;
} 